<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <link rel="stylesheet" href="css/prism.css">
  <style>
    html,
    body {
      box-sizing: border-box;
      margin: 0;
      padding: 0;
      height: 100%;
      font-size: 12px;
    }

    body {
      min-height: 500px;
    }

    section {
      display: flex;
      flex-wrap: wrap;
    }

    .code {
      margin-top: 3px;
    }

    pre[class*=language-] {
      margin: 0;
      padding: 0;
    }

    main {
      border-top: 2px solid #ccc;
      width: 100%;
      height: 50%;
      min-height: 200px;
    }

    input[type=text],
    input[type=number] {
      width: 100px;
    }
  </style>
  <title>平衡二叉搜索树-AVL</title>
</head>

<body>
  <section class="frames"></section>
  <section style="display: none;">
    <pre><code class="language-java">int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}</code></pre>
  </section>
  <main></main>
  <section>
    <div style='background-color:#f0ff1c; margin: 2px 2px 0 0; padding: 4px 6px;'>向上的</div>
    <div style='background-color:#ff371c; margin: 2px 2px 0 0; padding: 4px 6px;'>向下的</div>
    <div style='background-color:#00FF99; margin: 2px 2px 0 0; padding: 4px 6px;'>换爹的</div>
    <div style='background-color:#ccc; margin: 2px 2px 0 0; padding: 4px 6px;'>平衡</div>
  </section>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>数组表示的二叉树&nbsp;</span><input type="text" id='data' class="saveable array" value="4,2,6,1,3,5,7">
    <span>n&nbsp;</span><input type="text" id='n' class="saveable" value="5">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>待插入 key</span><input type="text" id='inserted' class="saveable" value="9">
    <input style='font-size:12px;' type="button" value="put" onclick="doPut()">
    <input style='font-size:12px;' type="button" value="LL 1" onclick="e2()">
    <input style='font-size:12px;' type="button" value="LL 2" onclick="e1()">
    <input style='font-size:12px;' type="button" value="LR" onclick="e4()">
    <input style='font-size:12px;' type="button" value="RR" onclick="e5()">
    <input style='font-size:12px;' type="button" value="RL" onclick="e6()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>待删除 key</span><input type="text" id='deleted' class="saveable" value="4">
    <input style='font-size:12px;' type="button" value="delete" onclick="doDelete()">
    <input style='font-size:12px;' type="button" value="LL 1" onclick="d1()">
    <input style='font-size:12px;' type="button" value="LL 2" onclick="d2()">
    <input style='font-size:12px;' type="button" value="LR 1" onclick="d3()">
    <input style='font-size:12px;' type="button" value="LR 2" onclick="d4()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <input style='font-size:12px;' type="button" value="不平衡" onclick="r00()">
    <input style='font-size:12px;' type="button" value="左旋树" onclick="r02()">
    <input style='font-size:12px;' type="button" value="右旋树" onclick="r01()">
    <input style='font-size:12px;' type="button" value="左右旋树" onclick="r03()">
    <input style='font-size:12px;' type="button" value="右左旋树" onclick="r04()">
    <input style='font-size:12px;' type="button" value="左旋" onclick="r1()">
    <input style='font-size:12px;' type="button" value="右旋" onclick="r2()">
    <input style='font-size:12px;' type="button" value="左右旋" onclick="r3()">
    <input style='font-size:12px;' type="button" value="右左旋" onclick="r4()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>动画速度(ms)&nbsp;</span><input type="number" step="100" value="300" id="animate_speed" class="saveable int"
      style="width: 40px;">
    <span>直径</span><input type="number" step="1" value="25" id="DIAMETER" class="saveable int" style="width: 40px;">
    <input style='font-size:12px;' type="button" value="保存" onclick="onSave('tree_avl')">
  </div>
  <script src="js/p5.js"></script>
  <script src="js/p5-svg.js"></script>
  <script src="js/util.js"></script>
  <script src="js/prism.js"></script>
  <script>
    function r00() {
      tree.root = new Node(4, 4, new Node(3, 3, new Node(2, 2, new Node(1, 1), null), null), null)
      // tree.root = new Node(3, 3, new Node(2, 2, new Node(1, 1), null), null)
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function r01() {
      tree.root = new Node(5, 4, new Node(3, 3, new Node(2, 2, new Node(1), null), new Node(4)), new Node(6))
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function r02() {
      tree.root = new Node(2, 4, new Node(1), new Node(4, 3, new Node(3), new Node(5, 2, null, new Node(6))))
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function r03() {
      tree.root = new Node(6, 4, new Node(2, 3, new Node(1), new Node(4, 2, new Node(3), new Node(5))), new Node(7))
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function r04() {
      tree.root = new Node(2, 4, new Node(1), new Node(6, 3, new Node(4, 2, new Node(3), new Node(5)), new Node(7)))
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function r1() {
      if (!tree.root.right)
        return
      const newRoot = tree.leftRotate(tree.root)
      all.pop()
      tree.root = newRoot
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      clearStatus(tree.root)
      d.updateFrameButtons()
    }
    function r2() {
      if (!tree.root.left)
        return
      const newRoot = tree.rightRotate(tree.root)
      all.pop()
      tree.root = newRoot
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      clearStatus(tree.root)
      d.updateFrameButtons()
    }
    function r3() {
      if (!tree.root.left)
        return
      const newRoot = tree.leftRightRotate(tree.root)
      all.pop()
      tree.root = newRoot
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      clearStatus(tree.root)
      d.updateFrameButtons()
    }
    function r4() {
      if (!tree.root.right)
        return
      const newRoot = tree.rightLeftRotate(tree.root)
      all.pop()
      tree.root = newRoot
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      clearStatus(tree.root)
      d.updateFrameButtons()
    }
    function d4() {
      tree.root = null
      all.pop()
      all.push(tree.root)
      const str = '6,2,7,1,4,8,3,5'
      document.getElementById("data").value = str
      document.getElementById("deleted").value = '8'
      const data = str.split(',').map(e => Number(e))
      for (let n of data) {
        tree.put(n)
      }
      d.updateFrameButtons()
    }
    function d3() {
      tree.root = null
      all.pop()
      all.push(tree.root)
      const str = '6,3,8,5'
      document.getElementById("data").value = str
      document.getElementById("deleted").value = '8'
      const data = str.split(',').map(e => Number(e))
      for (let n of data) {
        tree.put(n)
      }
      d.updateFrameButtons()
    }
    function d2() {
      // tree.root = null
      // all.pop()
      // all.push(tree.root)
      // const str = '14,9,19,5,12,16,20,21,15,17,13,7,3,7,18,10,11,6,8,2,4,1'
      // document.getElementById("data").value = str
      // document.getElementById("deleted").value = '9'
      // const data = str.split(',').map(e => Number(e))
      // for (let n of data) {
      //   tree.put(n)
      // }
      // d.updateFrameButtons()

      tree.root =
        new Node(14, 6,
          new Node(9, 5,
            new Node(5, 4,
              new Node(3, 3, new Node(2, 2, new Node(1), null), new Node(4)),
              new Node(7, 2, new Node(6), new Node(8))
            ),
            new Node(12, 3, new Node(10, 2, null, new Node(11)), new Node(13))
          ),
          new Node(19, 4,
            new Node(16, 3, new Node(15), new Node(17, 2, null, new Node(18))),
            new Node(20, 2, null, new Node(21))
          )
        )
      document.getElementById("deleted").value = '9'
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function d1() {
      tree.root = null
      all.pop()
      all.push(tree.root)
      const str = '6,3,8,1'
      document.getElementById("data").value = str
      document.getElementById("deleted").value = '8'
      const data = str.split(',').map(e => Number(e))
      for (let n of data) {
        tree.put(n)
      }
      d.updateFrameButtons()
    }
    function e1() {
      tree.root = new Node(8, 3, new Node(6, 2, new Node(5), new Node(7)), new Node(9))
      document.getElementById("inserted").value = '2'
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function e2() {
      tree.root = new Node(8, 2, new Node(6), null)
      document.getElementById("inserted").value = '3'
      all.pop()
      all.push(tree.root)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function e4() {
      tree.root = null
      all.pop()
      all.push(tree.root)
      const str = '8,9,3,1,4,5'
      document.getElementById("data").value = str
      const data = str.split(',').map(e => Number(e))
      for (let n of data) {
        tree.put(n)
      }
      d.updateFrameButtons()
    }
    function e5() {
      tree.root = null
      all.pop()
      all.push(tree.root)
      const str = '3,1,6,5,7,8'
      document.getElementById("data").value = str
      const data = str.split(',').map(e => Number(e))
      for (let n of data) {
        tree.put(n)
      }
      d.updateFrameButtons()
    }
    function e6() {
      tree.root = null
      all.pop()
      all.push(tree.root)
      const str = '3,1,6,5,9,4'
      document.getElementById("data").value = str
      const data = str.split(',').map(e => Number(e))
      for (let n of data) {
        tree.put(n)
      }
      d.updateFrameButtons()
    }
    const options = loadOptionsFromStorage('tree_avl')
    let data = options.data
    const DIAMETER = options.DIAMETER
    const n = options.n
    const d = new Draw(options.animate_speed)

    function setup() {
      const WIN_WIDTH = document.querySelector('main').clientWidth
      const WIN_HEIGHT = document.querySelector('main').clientHeight
      const FONT_SIZE = 12
      createCanvas(WIN_WIDTH, WIN_HEIGHT, SVG)
      textSize(FONT_SIZE)
      textAlign(CENTER)
      d.add({ cloned: clone(all) }, frame)
      d.updateFrameButtons()
    }
    function draw() {
      d.draw(() => background('#eee'))
    }
    function frame({ cloned }) {
      for (let i = 0; i < cloned.length; i++) {
        const node = cloned[i]
        drawTree(node, width / 2, DIAMETER / 2 + 10 + i * 120, n - 1, 0, 0)
      }
    }

    const subs = ['₀', '₁', '₂', '₃', '₄', '₅', '₆', '₇', '₈', '₉']
    function drawTree(node, x, y, deep, px, py) {
      if (node) {
        if (node.key) {
          if (px && py) {
            stroke(0)
            line(x, y, px, py)
          }
        }
        drawTree(node.left, x - Math.pow(2, deep) * DIAMETER / 4, y + Math.pow(2, n - deep) * DIAMETER / 5, deep - 1, x, y)
        drawTree(node.right, x + Math.pow(2, deep) * DIAMETER / 4, y + Math.pow(2, n - deep) * DIAMETER / 5, deep - 1, x, y)
        if (node.key) {
          let color = "#ccc"
          if ((node.status & 1) === 1) { color = "#ff371c" }
          if ((node.status & 2) === 2) { color = "#f0ff1c" }
          if ((node.status & 4) === 4) { color = "#00FF99" }
          stroke(0)
          fill(color)
          circle(x, y, DIAMETER)
          fill('black')
          noStroke()
          text(`${node.key}_${subs[node.height]}`, x, y + 4)
        }
      }
    }

    function doPut() {
      clearStatus(tree.root)
      const key = Number(document.getElementById("inserted").value)
      tree.put(key)
      d.updateFrameButtons()
    }

    function doDelete() {
      clearStatus(tree.root)
      const key = Number(document.getElementById("deleted").value)
      tree.remove(key)
      d.updateFrameButtons()
    }

    function clearStatus(node) {
      if (!node) {
        return
      }
      node.status = 0
      clearStatus(node.left)
      clearStatus(node.right)
    }

    class Node {
      constructor(key, height, left, right) {
        this.key = key
        this.height = height ?? 1
        this.left = left ?? null
        this.right = right ?? null
      }
    }

    class Tree {
      constructor() {
        this.root = null
      }
      remove(key) {
        const newRoot = this.doRemove(this.root, key)
        if (newRoot != this.root) {
          all.pop()
          all.push(newRoot)
        }
        d.add({ cloned: clone(all) }, frame)
        this.root = newRoot
        clearStatus(tree.root)
        d.add({ cloned: clone(all) }, frame)
      }
      doRemove(node, key) {
        if (node == null) {
          return null
        }
        if (key < node.key) {
          node.left = this.doRemove(node.left, key)
        } else if (node.key < key) {
          node.right = this.doRemove(node.right, key)
        } else {
          if (node.left == null) {
            node = node.right
          } else if (node.right == null) {
            node = node.left
          } else {
            let s = node.right
            while (s.left != null) {
              s = s.left
            }
            s.right = this.doRemove(node.right, s.key)
            s.left = node.left
            // node.key = s.key // only for animate
            node.status |= 1 // only for animate
            node = s
          }
        }
        if (node == null) {
          return null
        }
        this.updateHeight(node)
        const v = this.balance(node, key)
        return v
      }
      put(key) {
        const newRoot = this.doPut(this.root, key)
        if (newRoot != this.root) {
          all.pop()
          all.push(newRoot)
        }
        d.add({ cloned: clone(all) }, frame)
        this.root = newRoot
        clearStatus(tree.root)
        d.add({ cloned: clone(all) }, frame)
      }
      doPut(node, key) {
        if (!node) {
          return new Node(key)
        }
        if (key < node.key) {
          node.left = this.doPut(node.left, key)
        } else if (node.key < key) {
          node.right = this.doPut(node.right, key)
        }
        // d.add({ cloned: clone(all) }, frame)
        this.updateHeight(node)
        const r = this.balance(node, key)
        return r
      }
      balance(node, key) {
        if (node == null) {
          return null
        }
        const bf = this.bf(node)
        if (bf > 1 && this.bf(node.left) >= 0) {
          const r = this.rightRotate(node)
          return r
        }
        if (bf > 1 && this.bf(node.left) < 0) {
          const r = this.leftRightRotate(node)
          return r
        }
        if (bf < -1 && this.bf(node.right) <= 0) {
          const r = this.leftRotate(node)
          return r
        }
        if (bf < -1 && this.bf(node.right) > 0) {
          const r = this.rightLeftRotate(node)
          return r
        }
        return node
      }
      bf(node) {
        return this.height(node.left) - this.height(node.right)
      }
      updateHeight(node) {
        node.height = Math.max(this.height(node.left), this.height(node.right)) + 1
      }
      height(node) {
        return (node === null || node === undefined) ? 0 : node.height
      }
      leftRotate(r) {
        const a = r.right
        const b = a.left
        r.status |= 1
        a.status |= 2
        if (b) {
          b.status |= 4
        }
        d.add({ cloned: clone(all) }, frame)
        a.left = r
        r.right = b
        this.updateHeight(r)
        this.updateHeight(a)
        return a
      }
      rightRotate(r) {
        const a = r.left
        const b = a.right
        r.status |= 1
        a.status |= 2
        if (b) {
          b.status |= 4
        }
        d.add({ cloned: clone(all) }, frame)
        a.right = r
        r.left = b
        this.updateHeight(r)
        this.updateHeight(a)
        return a
      }
      leftRightRotate(p) {
        p.left = this.leftRotate(p.left)
        d.add({ cloned: clone(all) }, frame)
        clearStatus(p)
        return this.rightRotate(p)
      }
      rightLeftRotate(p) {
        p.right = this.rightRotate(p.right)
        d.add({ cloned: clone(all) }, frame)
        clearStatus(p)
        return this.leftRotate(p)
      }
    }
    const tree = new Tree()
    const all = []

  </script>
</body>

</html>